#!/usr/bin/python

gram = []
sym = []
class Rule(object):
	def __init__(self,line):
		object.__init__(self)
		if line.strip()=="":
			return None
		(l , r) = line.strip().split("->")
		self._lhs = l.strip()
		ws = r.split(" ")
		rs = []
		for w in ws:
			if w != "":
				rs.append(w)
		self._rhs = tuple(rs)
	def __str__(self):
		return self._lhs+" -> "+ " ".join(self._rhs)

def addRuleSym(r):
	global sym 
	if type(r) != Rule:
		return
	if r._lhs not in sym:
		sym.append(r._lhs)
	for w in r._rhs:
		if w.isupper() and w not in sym:
			sym.append(w)

# read in grammars
fgram=file("grammar.txt",'r')
lgram = fgram.readlines()
for l in lgram:
	#global grammar, sym
	r = Rule(l)
	gram.append(r)
	addRuleSym(r)
fgram.close()
sym.sort()

for i,w in enumerate(sym):
	print i,w

ff = file("test.txt",'r')
lines=ff.readlines()
ff.close()
r=len(sym)
lengram=len(gram)
for l in lines:
	words = l.split()
	n = len(words)
	p= [[[False for i in xrange(r)] for j in xrange(n+1) ] for k in xrange(n)]
	print "i:",len(p),"j:",len(p[0]),"k:",len(p[0][0])
	for x,word in enumerate(words):
		for y,rule in enumerate(gram):
			if len(rule._rhs) ==1 and cmp(word,rule._rhs[0]) == 0:
				#print "Unit Rule:",rule
				print "("+str(n)+","+str(r)+"):",x, 1, sym.index(rule._lhs)
				p[x][1][sym.index(rule._lhs)] = True
			else:
				pass #print "failed: ", (word),rule._rhs

	for i in xrange(2,n+1):
		for j in xrange(n-i+1):
			for k in xrange(1,i):
				print "==================="
				for x,rule in enumerate(gram):
					if len(rule._rhs) ==2 :
						(r1,r2)=rule._rhs
						l1=rule._lhs
						print "xxx",j,k,sym.index(r1),"--",j+k,i-k,sym.index(r2)
						if p[j][k][sym.index(r1)] and p[j+k][i-k][sym.index(r2)]:
						#print "new:",j,i,sym.index(l1)
							p[j][i][sym.index(l1)] = True
					elif len(rule._rhs) == 1 and rule._rhs[0].isupper() and p[j][k][sym.index(rule._rhs[0])] :
						print rule
						p[j][k][sym.index(rule._lhs)] = True
					#print rule

	for w in words:
		print w,
	print "\n"
	recog = False
	for j in xrange(0,n+1):
		mm = []
		for i in xrange(n):
			nn = []
			for k in xrange(r):
				if p[i][j][k]:
					#print j,i,k
					recog = True
					nn.append(sym[k])
			mm.append("|".join(nn))
			if not recog:
				mm.append("--")
			recog = False
		print " ".join(mm)+"\n"
